/**
 * 128. 最长连续序列
 * https://leetcode-cn.com/problems/longest-consecutive-sequence/
 */

// /**
//  * 快排
//  * @param {number[]} nums
//  * @param {number} begin
//  * @param {number} end
//  */
// function quickSort(nums, begin, end) {
//   if (begin >= end) return;
//   const base = nums[begin];
//   let left = begin;
//   let right = end;
//   let temp;
//   while (left < right) {
//     while (left < right && nums[right] >= base) {
//       right -= 1;
//     }
//     while (left < right && nums[left] <= base) {
//       left += 1;
//     }
//     temp = nums[left];
//     nums[left] = nums[right];
//     nums[right] = temp;
//   }
//   nums[begin] = nums[left];
//   nums[left] = base;
//   quickSort(nums, begin, left - 1);
//   quickSort(nums, left + 1, end);
// }

// /**
//  * @param {number[]} nums
//  * @return {number}
//  */
// function longestConsecutive(nums) {
//   if (!nums.length) return 0;
//   nums.sort((a, b) => a - b);
//   let max = 1;
//   let left = 0;
//   for (let i = 1; i < nums.length; i += 1) {
//     if (nums[i] - nums[i - 1] > 1) {
//       max = Math.max(max, i - left);
//       left = i;
//     } else if (nums[i] === nums[i - 1]) {
//       left += 1;
//     }
//   }
//   if (left < nums.length - 1) {
//     max = Math.max(max, nums.length - left);
//   }
//   return max;
// }

/**
 * @param {number[]} nums
 * @return {number}
 */
function longestConsecutive(nums) {
  if (!nums.length) return 0;
  const set = new Set();
  for (let i = 0; i < nums.length; i += 1) {
    set.add(nums[i]);
  }
  let max = 1;
  let cur = 1;
  let num;
  for (let i = 0; i < nums.length; i += 1) {
    num = nums[i];
    if (!set.has(num - 1)) {
      cur = 1;
      while (set.has(num + 1)) {
        cur += 1;
        num += 1;
      }
      max = Math.max(max, cur);
    }
  }
  return max;
}

console.log(longestConsecutive([100, 4, 200, 1, 3, 2]) === 4);
console.log(longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]) === 9);
console.log(longestConsecutive([]) === 0);
console.log(longestConsecutive([1]) === 1);
console.log(longestConsecutive([1, 2, 0, 1]) === 3);
